package com.mccken.practice.top100.Top_1$20.Top_26;

import com.mccken.practice.top100.ListNode;
import com.mccken.practice.top100.ListNodeUtil;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-02-14 19:11
 **/
public class MergeTwoLists {
	public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
		return null;
	}
	
	// 可以修改原节点
	public ListNode mergeTwoLists3(ListNode list1, ListNode list2) {
		if (list1 == null) {
			return list2;
		} else if (list2 == null) {
			return list1;
		} else if (list1.val < list2.val) {
			list1.next = mergeTwoLists3(list1.next, list2);
			return list1;		
		} else {
			// 本次递归动作
			list2.next = mergeTwoLists3(list1, list2.next);
			// 上次递归的结果
			return list2;
		}
	}
	public ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
		if (list1 == null) {
			return list2;
		}
		
		if (list2 == null) {
			return list1;
		}

		ListNode node1 = list1;
		ListNode node2 = list2;
		// todo 确定 head     
		ListNode node = new ListNode(-101);
		ListNode todoDelete = node;
		ListNode head = null;
		while (node1 != null && node2 != null) {
			if (node1.val < node2.val) {
				node.next = new ListNode(node1.val);
				node1 = node1.next;
			} else {
				node.next = new ListNode(node2.val);
				node2 = node2.next;
			}

			node = node.next;
			if (head == null) {
				head = node;
				todoDelete.next = null;
			}
		}

		while (node1 != null) {
			node.next = new ListNode(node1.val);
			node1 = node1.next;
			node = node.next;
		}
		while (node2 != null) {
			node.next = new ListNode(node2.val);
			node2 = node2.next;
			node = node.next;
		}
		
		return head;
	}

	public static void main(String[] args) {
		ListNode listNode1 = ListNodeUtil.buildListNode(new int[]{1});
		ListNode listNode2 = ListNodeUtil.buildListNode(new int[]{});

		ListNodeUtil.printListNode(listNode1);
		ListNodeUtil.printListNode(listNode2);

		MergeTwoLists m = new MergeTwoLists();
		ListNode listNode = m.mergeTwoLists(listNode1, listNode2);
		ListNodeUtil.printListNode(listNode);
	}
}
